// 24. 回文链表
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    // 思路：使用快慢指针找到链表的中点，然后反转后半部分链表，再依次比较前后两个链表的节点值是否相等
    bool isPalindrome(ListNode *head)
    {
        ListNode *slow = head;
        ListNode *fast = head->next;
        while (fast && fast->next) // 找到中点
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode *head2 = relistnode(slow->next); // 反转后半部分链表
        while (head2)                             // 从第二个链表开始比较，因为第一个链表可能比第二个链表长一个节点
                                                  // 为什么不需要检查两个链表是否同时结束？
                                                  // 奇数长度链表：前半部分会比后半部分多一个节点（中间节点）
                                                  //  偶数长度链表：两部分长度相等
        {
            if (head->val == head2->val)
            {
                head = head->next;
                head2 = head2->next;
            }
            else
            {
                return false;
            }
        }

        return true;
    }
    ListNode *relistnode(ListNode *node)
    {
        ListNode *prev = nullptr;
        ListNode *cur = node;
        while (cur)
        {
            ListNode *temp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
};